package com.example.mykotlinapp.test

import kotlin.math.max


/**
 *给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:
-1,0,-2
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
 *
 * @author zhudeshuai
 * @since 2019/8/8
 */


fun maxSubArray(nums: IntArray): Int {
    var max: Int = nums[0]
    for (i in 0 until nums.size) {
        var sum = nums[i]
        max = kotlin.math.max(sum, max)
        if (i == nums.size - 1) {
            //最后一个
            return kotlin.math.max(nums[i], max)
        }
        for (j in i + 1 until nums.size) {
            sum += nums[j]
            max = kotlin.math.max(sum, max)
        }
    }
    return max
}

fun maxSubArray2(nums: IntArray): Int {
    var result: Int = nums[0]
    var sum: Int = 0
    nums.forEach {
        if (sum < 0) {
            sum = it
        } else {
            sum += it
        }
        result = kotlin.math.max(result, sum)
    }
    return result
}


fun main() {
    val target = intArrayOf(1)
    print(maxSubArray2(target))
}